// m

// 给定一棵二叉树的根节点root
// 要求将这棵二叉树转换为一个已排序的双向循环链表，要求不能创建新的节点，只能调整树中节点指针的指向

// 解题思路
// 通过中序递归遍历可以将二叉树升序排列输出，这道题需要在中序遍历的同时，将节点的左右指向进行改变，使用head，tail存放双向链表的头尾节点，然后从根节点开始，进行
// 中序递归遍历

// 具体做法：
// 如果当前节点为空，直接返回
// 如果当前节点不为空，
//     递归遍历左子树
//     如果尾结点不为空，则将尾结点与当前节点进行连接
//     如果尾结点为空，则初始化头节点
//     将当前节点标记为尾结点
//     递归遍历右子树
// 最后将头节点和尾结点进行连接进行连接

function treeToDoubleList(root) {
    function dfs(node) {
        if (!node) {
            return null
        }
        dfs(node.left)
        if (tail) {
            tail.right = node
            node.left = tail
        } else {
            head = node
        }
        tail = node
        dfs(node.right)
    }
    if (!root) {
        return null
    }
    let head = null
    let tail = null
    dfs(root)
    head.left = tail
    tail.right = head
    return head
}

const root = {
    val: 4,
    left: {
        val: 3,
        left: {
            val: 2,
        },
        right: {
            val: 3.5,
        },
    },
    right: {
        val: 6,
    },
};

console.log(treeToDoubleList(root))